package chunzhao.Jun_20;

/**
 * @Classname TopK
 * @Description TODO
 * @Date 2024/1/20 15:47
 * @Created by ZHL17
 */

/**
 * Top的二分+快排解法
 */
public class TopK {
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5,6,7,8,9};
        int k = 4;
        System.out.println(binary(nums,0,nums.length - 1,k));
    }
    public static int binary(int[] nums, int left, int right, int k) {
        int l = left;
        int r = right;
        while (l <= r) {
            int index = quickSort(nums, l, r);
            if (nums.length - index == k) {
                return nums[index];
            } else if (nums.length - index > k) {
                l = index + 1;
            } else {
                r = index - 1;
            }
        }
        return -1;
    }
    public static int quickSort(int[] nums, int left, int right) {
        if (left >= right) return left;
        int l = left;
        int r = right;
        while (l < r) {
            while (l < r && nums[r] >= nums[left]) r--;
            while (l < r && nums[l] <= nums[left]) l++;
            swap(nums, l, r);
        }
        swap(nums,l,left);
        return l;

    }
    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
